package main

import "fmt"

func sortColors(nums []int) {
	// 区间 [0..left] 代表0
	// 区间 [left+1..i] 代表1
	// 区间 [right..len-1] 代表2
	// 0 2 1 1 2
	left, right := -1, len(nums)
	for i := 0; i < right; {
		if nums[i] == 1 {
			i++
		} else if nums[i] == 2 {
			right--
			// 把2放到后面-交换
			nums[i], nums[right] = nums[right], nums[i]
		} else {
			// 为1,加入到
			left++
			nums[i], nums[left] = nums[left], nums[i]
			i++
		}
	}
}

func sortColorsV2(nums []int) {
	// 左记0,右记2
	left, right := 0, len(nums)-1
	for i := left; i <= right; {
		// left指待检查元素, right存待检查元素 => 从left开始,值为1
		if nums[i] == 0 {
			// 检测到是0,则交换后,两个都前进一步
			nums[left], nums[i] = nums[i], nums[left]
			i++
			left++
		} else if nums[i] == 2 {
			nums[right], nums[i] = nums[i], nums[right]
			right--
		} else {
			i++
		}
	}
}

func sortColorsV1(nums []int) {
	// 先计数
	m := make(map[int]int, 3)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}

	index := 0

	// 再覆盖
	for _, k := range []int{0, 1, 2} {
		v := m[k]
		for i := 0; i < v; i++ {
			nums[index] = k
			index++
		}
	}
}

func main() {
	nums := []int{2, 0, 2, 1, 1, 0}
	sortColors(nums)

	fmt.Println(nums)
}
